51. N 皇后

Similar Question

Solution Tips

方案一: 模拟 + 回溯

var solveNQueens = function (n) {
    // 皇后的攻击范围是四面八方的
    // 据说这道题是经典的回溯法, 那就来个极致的暴力美学
    // 可以把矩阵一维化, 但是有点费脑子
    const matrix = new Array(n).fill('').map(() => new Array(n).fill('.'));
    const res = [];
    backtracking([], 0)
    return res;

    // 回溯的去找下一个可以放下Q的位置
    // 一行行的找是比较科学的
    // 如果这一行放不下了就去到下一行, 好像列也可以一起来?
    function backtracking(chosen, row) {
        if (chosen.length === n) {
            res.push(matrix.map(row => row.join('')));
            return;
        }
        // 只需要检查 curRow 即可
        for (let col = 0; col < n; col++) {
            if (matrix[row][col] === "." && valid(chosen, row, col)) {
                chosen.push([row, col]);
                matrix[row][col] = "Q";
                // 这一行, 这一列都放不下新的皇后了, 好像改变标记会好点?
                // 但是那样的话回退的时候也需要清除标记
                // 标记的更改和清除太耗时间了, 行和列其实不耗时间, 耗时间的是对角线的两个
                // 可以考虑更新 validCol? 这样只需要判断45就可以了, 但是感觉也节省不了多少
                backtracking(chosen, row + 1);
                chosen.pop();
                matrix[row][col] = ".";
            }
        }
    }

    function valid(chosen, row, col) {
        // 只要有一个不符合就返回
        for (let i = 0; i < chosen.length; i++) {
            const [x, y] = chosen[i];
            // 不能同行, 同列
            if (col === y) {
                return false;
            }

            // 45度 方位也不行
            if (Math.abs(row - x) === Math.abs(col - y)) {
                return false;
            }

        }
        // 这样子重复的检查太多了, 还是不如每次只保留剩余的格子?
        // 因为 n 行要放置 n 个, 所以每一行一定会有一个, 所以其实只需要回溯一行就可以了
        // 行确定之后, 就可以确定剩余的列, 再检测45的位置就好了?
        return true;
    }
};

方案一优化: 甄别回溯类型 + 合法判断优化

由于每个皇后必须位于不同列，因此已经放置的皇后所在的列不能放置别的皇后。第一个皇后有 N 列可以选择，第二个皇后最多有

N−1 列可以选择，第三个皇后最多有 N−2 列可以选择（如果考虑到不能在同一条斜线上，可能的选择数量更少），因此所有可能的情况不会超过 N! 种，遍历这些情况的时间复杂度是 O(N!)。

为了降低总时间复杂度，每次放置皇后时需要快速判断每个位置是否可以放置皇后，显然，最理想的情况是在 O(1) 的时间内判断该位置所在的列和两条斜线上是否已经有皇后。

以下两种方法分别使用集合和位运算对皇后的放置位置进行判断，都可以在 O(1) 的时间内判断一个位置是否可以放置皇后，算法的总时间复杂度都是 O(N!)。

方法一：基于集合的回溯

为了判断一个位置所在的列和两条斜线上是否已经有皇后，使用三个集合 columns、 diagonals 1 和 diagonals 2 ​ 分别记录每一列以及两个方向的每条斜线上是否有皇后。

列的表示法很直观，一共有 N 列，每一列的下标范围从 0 到 N−1，使用列的下标即可明确表示每一列。

如何表示两个方向的斜线呢？对于每个方向的斜线，需要找到斜线上的每个位置的行下标与列下标之间的关系。 方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 (0,0) 和 (3,3) 在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。

每次放置皇后时，对于每个位置判断其是否在三个集合中，如果三个集合都不包含当前位置，则当前位置是可以放置皇后的位置。

方法二: 基于位运算的回溯

小结